#include <iostream>
#include <string.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using AdjacencyTable = std::vector<std::vector<int>>;
using VertexSet = std::set<int>;
using VertexGroup = std::vector<int>;
using Groups = std::vector<VertexGroup>;

Groups BrEAdthFirstSearch(AdjacencyTable& table);
Groups DepthFirstSearch(AdjacencyTable& table);
void ConnectedBrEAdthFirstSearch(int currentVertex, AdjacencyTable& table, VertexSet& searched, VertexGroup& result);
void ConnectedDepthFirstSearch(int beginVertex, AdjacencyTable& table, VertexSet& searched, VertexGroup& result);

Groups BrEAdthFirstSearch(AdjacencyTable& table)
{
	VertexSet searched;
	Groups groups;
	for (int i = 0; i < table.size(); ++i)
	{
		if (searched.find(i) == searched.end())
		{
			groups.push_back(VertexGroup());
			ConnectedBrEAdthFirstSearch(i, table, searched, groups.back());
		}
	}
	return groups;
}

Groups DepthFirstSearch(AdjacencyTable& table)
{
	VertexSet searched;
	Groups groups;
	for (int i = 0; i < table.size(); ++i)
	{
		if (searched.find(i) == searched.end())
		{
			groups.push_back(VertexGroup());
			ConnectedDepthFirstSearch(i, table, searched, groups.back());
		}
	}
	return groups;
}

// 搜索范围为一个连通的区域
void ConnectedBrEAdthFirstSearch(int currentVertex, AdjacencyTable& table, VertexSet& searched, VertexGroup& result)
{
	if (searched.find(currentVertex) != searched.end())
	{
		return;
	}
	searched.insert(currentVertex);
	result.push_back(currentVertex);
	for (auto adjacenctVertex : table[currentVertex])
	{
		ConnectedBrEAdthFirstSearch(adjacenctVertex, table, searched, result);
	}
}

// 搜索范围为一个连通的区域
void ConnectedDepthFirstSearch(int beginVertex, AdjacencyTable& table, VertexSet& searched, VertexGroup& result)
{
	std::queue<int> q;
	q.push(beginVertex);
	while (!q.empty())
	{
		int currentVertex = q.front();
		q.pop();
		if (searched.find(currentVertex) != searched.end())
		{
			continue;
		}
		searched.insert(currentVertex);
		result.push_back(currentVertex);
		for (auto adjacenctVertex : table[currentVertex])
		{
			q.push(adjacenctVertex);
		}
	}
}

void PrintGroups(Groups& groups)
{
	for (VertexGroup& group : groups)
	{
		std::cout << '{' << group.front();
		for (auto i = group.begin() + 1; i != group.end(); i++)
		{
			std::cout << ' ' << *i;
		}
		std::cout << '}';
	}
	std::cout << std::endl;
}

int main()
{
	int n, m;
	std::cin >> n >> m;
	AdjacencyTable adjTable;
	for (int i = 0; i < n; ++i)
	{
		adjTable.push_back(std::vector<int>());
	}
	for (int i = 0; i < m; ++i)
	{
		int v1, v2;
		std::cin >> v1 >> v2;
		adjTable[v1].push_back(v2);
		adjTable[v2].push_back(v1);
	}
	for (auto& line : adjTable)
	{
		std::sort(line.begin(), line.end());
	}

	auto bfsResult = BrEAdthFirstSearch(adjTable);
	PrintGroups(bfsResult);

	auto dfsResult = DepthFirstSearch(adjTable);
	PrintGroups(dfsResult);

	return 0;
}
